package com.wfm.niuke.dynamic;

import java.util.ArrayList;
import java.util.List;

public class BM74P剑指OfferII087复原IP {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return result; // 算是剪枝了
        StringBuilder sb = new StringBuilder(s);
        backTrack(sb, 0, 0);
        return result;
    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void backTrack(StringBuilder s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 逗点数量为3时，分隔结束
            // 判断第四段⼦字符串是否合法，如果合法就放进result中
            if (isValid(s,startIndex,s.length()-1)) {
                result.add(s.toString());
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s.insert(i+1,'.');
                backTrack(s, i + 2, pointNum+1);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
                s = s.deleteCharAt(i+1);
            } else {
                break;
            }
        }
    }

    boolean isValid(StringBuilder s, int start ,int end){
        if(start>end) return false;
        if(s.charAt(start)=='0'&&start!=end) return false;

        int num = 0;
        for (int i = 0; i <= end; i++) {
            if(s.charAt(i)>'9'||s.charAt(i)<'0') return false;
            num=num*10+s.charAt(i)-'0';
            if(num>2555) return false;
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new BM74P剑指OfferII087复原IP().new Solution();
        System.out.println(solution.restoreIpAddresses("19216811"));
    }
}